home *** CD-ROM | disk | FTP | other *** search
/ Visual Cafe 3 / Visual Cafe 3.ISO / Vcafe / Main.bin / CompactByteArray.java < prev    next >
Text File  |  1998-09-22  |  15KB  |  406 lines
  1. /*
  2.  * @(#)CompactByteArray.java    1.9 97/10/28
  3.  *
  4.  * (C) Copyright Taligent, Inc. 1996 - All Rights Reserved
  5.  * (C) Copyright IBM Corp. 1996 - All Rights Reserved
  6.  *
  7.  * Portions copyright (c) 1996 Sun Microsystems, Inc. All Rights Reserved.
  8.  *
  9.  *   The original version of this source code and documentation is copyrighted
  10.  * and owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These
  11.  * materials are provided under terms of a License Agreement between Taligent
  12.  * and Sun. This technology is protected by multiple US and International
  13.  * patents. This notice and attribution to Taligent may not be removed.
  14.  *   Taligent is a registered trademark of Taligent, Inc.
  15.  *
  16.  * Permission to use, copy, modify, and distribute this software
  17.  * and its documentation for NON-COMMERCIAL purposes and without
  18.  * fee is hereby granted provided that this copyright notice
  19.  * appears in all copies. Please refer to the file "copyright.html"
  20.  * for further important copyright and licensing information.
  21.  *
  22.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
  23.  * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
  24.  * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  25.  * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
  26.  * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
  27.  * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
  28.  *
  29.  */
  30.  
  31. package java.text;
  32.  
  33.  
  34. /**
  35.  * class CompactATypeArray : use only on primitive data types
  36.  * Provides a compact way to store information that is indexed by Unicode
  37.  * values, such as character properties, types, keyboard values, etc.This
  38.  * is very useful when you have a block of Unicode data that contains
  39.  * significant values while the rest of the Unicode data is unused in the
  40.  * application or when you have a lot of redundance, such as where all 21,000
  41.  * Han ideographs have the same value.  However, lookup is much faster than a
  42.  * hash table.
  43.  * A compact array of any primitive data type serves two purposes:
  44.  * <UL type = round>
  45.  *     <LI>Fast access of the indexed values.
  46.  *     <LI>Smaller memory footprint.
  47.  * </UL>
  48.  * A compact array is composed of a index array and value array.  The index
  49.  * array contains the indicies of Unicode characters to the value array.
  50.  *
  51.  * @see                CompactCharArray
  52.  * @see                CompactIntArray
  53.  * @see                CompactShortArray
  54.  * @see                CompactStringArray
  55.  * @version            1.9 10/28/97
  56.  * @author             Helena Shih
  57.  */
  58. final class CompactByteArray implements Cloneable {
  59.  
  60.     /**
  61.      * The total number of Unicode characters.
  62.      */
  63.     public static  final int UNICODECOUNT =65536;
  64.  
  65.     /**
  66.      * Default constructor for CompactByteArray, the default value of the
  67.      * compact array is 0.
  68.      */
  69.     public CompactByteArray()
  70.     {
  71.         this((byte)0);
  72.     }
  73.     /**
  74.      * Constructor for CompactByteArray.
  75.      * @param defaultValue the default value of the compact array.
  76.      */
  77.     public CompactByteArray(byte defaultValue)
  78.     {
  79.         int i;
  80.         values = new byte[UNICODECOUNT];
  81.         indices = new short[INDEXCOUNT];
  82.         for (i = 0; i < UNICODECOUNT; ++i) {
  83.             values[i] = defaultValue;
  84.         }
  85.         for (i = 0; i < INDEXCOUNT; ++i) {
  86.             indices[i] = (short)(i<<BLOCKSHIFT);
  87.         }
  88.         isCompact = false;
  89.     }
  90.     /**
  91.      * Constructor for CompactByteArray.
  92.      * @param indexArray the indicies of the compact array.
  93.      * @param newValues the values of the compact array.
  94.      * @exception IllegalArgumentException If index is out of range.
  95.      */
  96.     public CompactByteArray(short indexArray[],
  97.                             byte newValues[])
  98.     {
  99.         int i;
  100.         if (indexArray.length != INDEXCOUNT)
  101.             throw new IllegalArgumentException("Index out of bounds!");
  102.         for (i = 0; i < INDEXCOUNT; ++i) {
  103.             short index = indexArray[i];
  104.             if ((index < 0) || (index >= newValues.length+BLOCKCOUNT))
  105.                 throw new IllegalArgumentException("Index out of bounds!");
  106.         }
  107.         indices = indexArray;
  108.         values = newValues;
  109.         isCompact = false;
  110.     }
  111.     /**
  112.      * Get the mapped value of a Unicode character.
  113.      * @param index the character to get the mapped value with
  114.      * @return the mapped value of the given character
  115.      */
  116.     public byte elementAt(char index)
  117.     {
  118.         return (values[(indices[index >> BLOCKSHIFT] & 0xFFFF)
  119.                        + (index & BLOCKMASK)]);
  120.     }
  121.     /**
  122.      * Set a new value for a Unicode character.
  123.      * Set automatically expands the array if it is compacted.
  124.      * @param index the character to set the mapped value with
  125.      * @param value the new mapped value
  126.      */
  127.     public void setElementAt(char index, byte value)
  128.     {
  129.         if (isCompact)
  130.             expand();
  131.         values[(int)index] = value;
  132.     }
  133.     /**
  134.      * Set new values for a range of Unicode character.
  135.      * @param start the starting offset of the range
  136.      * @param end the ending offset of the range
  137.      * @param value the new mapped value
  138.      */
  139.     public void setElementAt(char start, char end, byte value)
  140.     {
  141.         int i;
  142.         if (isCompact) {
  143.             expand();
  144.         }
  145.         for (i = start; i <= end; ++i) {
  146.             values[i] = value;
  147.         }
  148.     }
  149.     /**
  150.       *Compact the array.
  151.       */
  152.     public void compact()
  153.     {
  154.         if (isCompact == false) {
  155.             char[]      tempIndex;
  156.             int                     tempIndexCount;
  157.             byte[]          tempArray;
  158.             short           iBlock, iIndex;
  159.  
  160.             // make temp storage, larger than we need
  161.             tempIndex = new char[UNICODECOUNT];
  162.             // set up first block.
  163.             tempIndexCount = BLOCKCOUNT;
  164.             for (iIndex = 0; iIndex < BLOCKCOUNT; ++iIndex) {
  165.                 tempIndex[iIndex] = (char)iIndex;
  166.             }; // endfor (iIndex = 0; .....)
  167.             indices[0] = (short)0;
  168.  
  169.             // for each successive block, find out its first position
  170.             // in the compacted array
  171.             for (iBlock = 1; iBlock < INDEXCOUNT; ++iBlock) {
  172.                 int     newCount, firstPosition, block;
  173.                 block = iBlock<<BLOCKSHIFT;
  174.                 if (DEBUGSMALL) if (block > DEBUGSMALLLIMIT) break;
  175.                 firstPosition = FindOverlappingPosition( block, tempIndex,
  176.                                                          tempIndexCount );
  177.  
  178.                 newCount = firstPosition + BLOCKCOUNT;
  179.                 if (newCount > tempIndexCount) {
  180.                     for (iIndex = (short)tempIndexCount;
  181.                          iIndex < newCount;
  182.                          ++iIndex) {
  183.                         tempIndex[iIndex] = (char)
  184.                                             (iIndex - firstPosition + block);
  185.                     } // endfor (iIndex = tempIndexCount....)
  186.                     tempIndexCount = newCount;
  187.                 } // endif (newCount > tempIndexCount)
  188.                 indices[iBlock] = (short)firstPosition;
  189.             } // endfor (iBlock = 1.....)
  190.  
  191.             // now allocate and copy the items into the array
  192.             tempArray = new byte[tempIndexCount];
  193.             for (iIndex = 0; iIndex < tempIndexCount; ++iIndex) {
  194.                 tempArray[iIndex] = values[tempIndex[iIndex]];
  195.             }
  196.             values = null;
  197.             values = tempArray;
  198.             isCompact = true;
  199.         } // endif (isCompact != false)
  200.     }
  201.     /** For internal use only.  Do not modify the result, the behavior of
  202.       * modified results are undefined.
  203.       */
  204.     public short getIndexArray()[]
  205.     {
  206.         return indices;
  207.     }
  208.     /** For internal use only.  Do not modify the result, the behavior of
  209.       * modified results are undefined.
  210.       */
  211.     public byte getStringArray()[]
  212.     {
  213.         return values;
  214.     }
  215.     /**
  216.      * Overrides Cloneable
  217.      */
  218.     public Object clone()
  219.     {
  220.         try {
  221.             CompactByteArray other = (CompactByteArray) super.clone();
  222.             other.values = (byte[])values.clone();
  223.             other.indices = (short[])indices.clone();
  224.             return other;
  225.         } catch (CloneNotSupportedException e) {
  226.             throw new InternalError();
  227.         }
  228.     }
  229.     /**
  230.      * Compares the equality of two compact array objects.
  231.      * @param obj the compact array object to be compared with this.
  232.      * @return true if the current compact array object is the same
  233.      * as the compact array object obj; false otherwise.
  234.      */
  235.     public boolean equals(Object obj) {
  236.         if (obj == null) return false;
  237.         if (this == obj)                      // quick check
  238.             return true;
  239.         if (getClass() != obj.getClass())         // same class?
  240.             return false;
  241.         CompactByteArray other = (CompactByteArray) obj;
  242.         for (int i = 0; i < UNICODECOUNT; i++) {
  243.             // could be sped up later
  244.             if (elementAt((char)i) != other.elementAt((char)i))
  245.                 return false;
  246.         }
  247.         return true; // we made it through the guantlet.
  248.     }
  249.  
  250.     /**
  251.      * Generates the hash code for the compact array object
  252.      */
  253.  
  254.     public int hashCode() {
  255.         int result = 0;
  256.         int increment = Math.min(3, values.length/16);
  257.         for (int i = 0; i < values.length; i+= increment) {
  258.             result = result * 37 + values[i];
  259.         }
  260.         return result;
  261.     }
  262.     // --------------------------------------------------------------
  263.     // package private
  264.     // --------------------------------------------------------------
  265.     void writeArrays()
  266.     {
  267.         int i;
  268.         int cnt = (values.length > 0) ? values.length :
  269.             values.length+UNICODECOUNT;
  270.         System.out.println("{");
  271.         for (i = 0; i < INDEXCOUNT-1; i++)
  272.         {
  273.             System.out.print("(short)"
  274.                              + ((indices[i] >= 0) ?
  275.                                 (int)indices[i] :
  276.                                 (int)(indices[i]+UNICODECOUNT))
  277.                              + ", ");
  278.             if (i != 0)
  279.                 if (i % 10 == 0)
  280.                     System.out.println();
  281.         }
  282.         System.out.println("(short)"
  283.                            + ((indices[INDEXCOUNT-1] >= 0) ?
  284.                               (int)indices[i] :
  285.                               (int)(indices[i]+UNICODECOUNT))
  286.                            + " }");
  287.         System.out.println("{");
  288.         for (i = 0; i < cnt-1; i++)
  289.         {
  290.             System.out.print("(byte)" + (int)values[i] + ", ");
  291.             if (i != 0)
  292.                 if (i % 10 == 0)
  293.                     System.out.println();
  294.         }
  295.         System.out.println("(byte)" + (int)values[cnt-1] + " }");
  296.     }
  297.     // Print char Array  : Debug only
  298.     void printIndex(short start, short count)
  299.     {
  300.         int i;
  301.         for (i = start; i < count; ++i)
  302.         {
  303.             System.out.println(i + " -> : " +
  304.                                (int)((indices[i] >= 0) ?
  305.                                      indices[i] :
  306.                                      indices[i] + UNICODECOUNT));
  307.         }
  308.         System.out.println();
  309.     }
  310.     void printPlainArray(int start,int count, char[] tempIndex)
  311.     {
  312.         int iIndex;
  313.         if (tempIndex != null)
  314.         {
  315.             for (iIndex     = start; iIndex < start + count; ++iIndex)
  316.             {
  317.                 System.out.print(" " + (int)values[tempIndex[iIndex]]);
  318.             }
  319.         }
  320.         else
  321.         {
  322.             for (iIndex = start; iIndex < start + count; ++iIndex)
  323.             {
  324.                 System.out.print(" " + (int)values[iIndex]);
  325.             }
  326.         }
  327.         System.out.println("    Range: start " + start + " , count " + count);
  328.     }
  329.     // --------------------------------------------------------------
  330.     // private
  331.     // --------------------------------------------------------------
  332.     /**
  333.       * Expanding takes the array back to a 65536 element array.
  334.       */
  335.     private void expand()
  336.     {
  337.         int i;
  338.         if (isCompact) {
  339.             byte[]  tempArray;
  340.             tempArray = new byte[UNICODECOUNT];
  341.             for (i = 0; i < UNICODECOUNT; ++i) {
  342.                 tempArray[i] = elementAt((char)i);
  343.             }
  344.             for (i = 0; i < INDEXCOUNT; ++i) {
  345.                 indices[i] = (short)(i<<BLOCKSHIFT);
  346.             }
  347.             values = null;
  348.             values = tempArray;
  349.             isCompact = false;
  350.         }
  351.     }
  352.     // # of elements in the indexed array
  353.     private short capacity()
  354.     {
  355.         return (short)values.length;
  356.     }
  357.     private byte[] getArray()
  358.     {
  359.         return values;
  360.     }
  361.     private int
  362.     FindOverlappingPosition(int start, char[] tempIndex, int tempIndexCount)
  363.     {
  364.         int i;
  365.         short j;
  366.         short currentCount;
  367.  
  368.         if (DEBUGOVERLAP && start < DEBUGSHOWOVERLAPLIMIT) {
  369.             printPlainArray(start, BLOCKCOUNT, null);
  370.             printPlainArray(0, tempIndexCount, tempIndex);
  371.         }
  372.         for (i = 0; i < tempIndexCount; i += BLOCKCOUNT) {
  373.             currentCount = (short)BLOCKCOUNT;
  374.             if (i + BLOCKCOUNT > tempIndexCount) {
  375.                 currentCount = (short)(tempIndexCount - i);
  376.             }
  377.             for (j = 0; j < currentCount; ++j) {
  378.                 if (values[start + j] != values[tempIndex[i + j]]) break;
  379.             }
  380.             if (j == currentCount) break;
  381.         }
  382.         if (DEBUGOVERLAP && start < DEBUGSHOWOVERLAPLIMIT) {
  383.             for (j = 1; j < i; ++j) {
  384.                 System.out.print(" ");
  385.             }
  386.             printPlainArray(start, BLOCKCOUNT, null);
  387.             System.out.println("    Found At: " + i);
  388.         }
  389.         return i;
  390.     }
  391.     private static  final int DEBUGSHOWOVERLAPLIMIT = 100;
  392.     private static  final boolean DEBUGTRACE = false;
  393.     private static  final boolean DEBUGSMALL = false;
  394.     private static  final boolean DEBUGOVERLAP = false;
  395.     private static  final int DEBUGSMALLLIMIT = 30000;
  396.     private static  final int BLOCKSHIFT =7;
  397.     private static  final int BLOCKCOUNT =(1<<BLOCKSHIFT);
  398.     private static  final int INDEXSHIFT =(16-BLOCKSHIFT);
  399.     private static  final int INDEXCOUNT =(1<<INDEXSHIFT);
  400.     private static  final int BLOCKMASK = BLOCKCOUNT - 1;
  401.  
  402.     private byte[] values;  // char -> short (char parameterized short)
  403.     private short indices[];
  404.     private boolean isCompact;
  405. };
  406.